- Title
- The complexity ecology of parameters: an illustration using bounded max leaf number
- Creator
- Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket
- Relation
- Theory of Computing Systems Vol. 45, Issue 4, p. 822-848
- Publisher Link
- http://dx.doi.org/10.1007/s00224-009-9167-9
- Publisher
- Springer-Verlag
- Resource Type
- journal article
- Date
- 2009
- Description
- In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or wellunderstood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-COLORING, HAMILTON PATH, MINIMUM DOMINATING SET, MINIMUM BANDWIDTH or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things: (1) We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G) ≤ k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O*(f (k)). (2) The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.
- Subject
- parameterized complexity; max leaf; bandwidth; well quasiordering; kernelization
- Identifier
- http://hdl.handle.net/1959.13/809098
- Identifier
- uon:7825
- Identifier
- ISSN:1432-4350
- Language
- eng
- Reviewed
- Hits: 3769
- Visitors: 3690
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|